Maze Generation
I must have some sort of fascination with maze generation. Such a small amount of logic can generate complex and interesting puzzles.
In this project, I explain the maze making approach with multiple layers of generation, with interactive examples
In this project, each layer uses generator functions to update the current state progressively. This way you can watch it all come together. You can modify parameters of each layer and/or just click refresh and it will regenerate from that layer onward
Interactive demo
Layers
1. Initialisation Layer
This one is easy. On a 2D grid, set every "tile" to solid except where x % 2 === 0 || y % 2 === 0. For those tiles, set them to non-solid, and give each a unique room id.
The room id is used to record unconnected islands. The goal of the maze generation is to join them all.
2. Room Layer
Before we join the rooms, we can add larger rooms. This layer places random rectangles over the 2D grid, and merges the room ids. The merging is critical so that the maze still behaves like a maze, without any loops.
The rooms start on odd x and y coordinates, with odd heights and widths, so they align with the current non-solid tiles. There are parameters for the max height and width, as well as the number of rooms.
Its worth noting that these larger rooms can overlap others, making more interesting shapes. There's some logic to make a few extra attempts to avoid this overlap, but it still happens.
3. Maze Solver
This is the main logic of creating mazes. The goal of this layer is to join all the rooms together if they are not already joined.
First we find all solid tiles that sit between two separate rooms, and then shuffle them.
We then progress through the queue processing the tiles one-by-one. If the tile still separates two unique room ids, its turned to non-solid and adopts the higher room id. The lower room id is replaced with the higher id, we loop through the whole maze as each room will grow as the algorithm progresses.
4. End Trimmer
Naturally you end up with a lot of dead ends in the maze. This layer progressively turns dead ends back to solid tiles, effectively shortening these dead ends. If this runs too much you just end up with the big rooms and connecting hallways. If you don't run it at all, you get lots of little halways branching everywhere.
There's a parameter to control how many iterations this runs for
5. Identifier Layer
This stage goes through the whole maze, and asseses the neighbours of each tile. If you can make a 2x2 square of non-solid tiles, then it must be part of a "room", otherwise it must be a "hallway". then finally, any hallway that borders a room, is a "doorway"
6. Farthest Path calculator
This layer works out the two farthest points, and the path between them. It starts with a random point in the maze, then uses Dijkstra's algorithm to calculate the distance to all the others.
Second, it picks the farthest point from our random starting point, and uses it as the new starting point, running the algorithm again.
Then we trace the path bettween those two points.
7. Door Layer
This finds all the doorways, and randomises whether they should be open or closed.
One door along the path detected in layer 6 will be locked
8. Key Layer
This layer runs Dijkstra's algorithm again, finding the farthest point from the path prior to the locked door. It then chooses the farthest tile to place the key.
This leads to backtracking gameplay, and incentivises discovery along the different paths. Also, it would be no fun if the key was just next to the locked door.
9. Entity Layer
I added this layer later in the process, and mainly exists for the game I made with it. It creates start/end endities, the player entity, door and key entities, and any enemies I want. If you're looking at the code, there's the concept of "items" from earlier layer that are probably redundant now, and I could tidy it up.